package dynamic;

public class BalancePartition {

	//given an array, try to partition them so that the two separate part have the closest sum
	//p[i][j] = 1 if some subset of a[0]..a[i] has sum of j else 0
	public static int bp(int[] array) {
		int k = LongestIncreasSeq.max(array);//just get the maximum element of the array
		int maxsum = k * array.length;
		int[][] p = new int[array.length][maxsum + 1];
		for (int j = 0; j <= maxsum; j++)
			p[0][j] = j == array[0] ? 1 : 0;
		
		//time complexity n^2*maxsum
		for (int i = 1; i < array.length; i++) {
			for (int j = 0; j <= maxsum; j++)
				if (j - array[i] > 0) {
					p[i][j] = Math.max(p[i - 1][j], p[i - 1][j - array[i]]);
				} else {
					p[i][j] = p[i - 1][j];
				}
		}
		//System.out.println( p);
		int sum = 0;

		for (int i = 0; i < array.length; i++)
			sum += array[i];

		sum = sum / 2;

		int min = sum;
		int subsum = 0;
		for (int j = 0; j <= maxsum; j++) {
			if (p[array.length - 1][j] == 1 && Math.abs(j - sum) < min) {
				min = Math.abs(j - sum);
				subsum = j;
			}
		}
		System.out.println(min);
		return subsum;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int array[] = { 2, 10, 3, 8, 5, 7, 9, 5, 3, 2 };
		System.out.println(bp(array));
	}

}
